package JZ36_两个链表的第一个公共结点;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int length1 = findListLenth(pHead1);
        int length2 = findListLenth(pHead2);

        if (length1 > length2){
            pHead1 = walk(pHead1, length1- length2);
        }else {
            pHead2 = walk(pHead2, length2 - length1);
        }

        while (pHead1 != null){
            if (pHead1 == pHead2){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }

        return null;
    }

    private ListNode walk(ListNode head, int n) {
        while (n > 0){
            head = head.next;
            n--;
        }
        return head;
    }

    private int findListLenth(ListNode head) {
        if (head == null){
            return 0;
        }
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
}